package sort;

/**
 * @author Europa
 * @create 2020-05-15 21:55
 */
public class Quick3way extends Sort {

    /**
     * 三向切分快速排序
     *
     * @param array int数组
     */
    @Override
    public void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int l = left;
        int mid = left + 1;
        int r = right;
        int value = array[left];
        while (mid <= r) {
            int i = Integer.compare(array[mid], value);
            if (i < 0) {
                exchange(array, l++, mid++);
                } else if (i > 0) {
                exchange(array, mid, r--);
                } else {
                mid++;
            }
        }
        sort(array, left, l - 1);
        sort(array, r + 1, right);
    }
}
